Home » Data Structure

Data Structure Searching Algorithms

Last updated : April 17, 2025

Data Structure Searching

Searching is the process of finding an element in a given list. In this process, we check whether an item is available in the list or not.

Types of Searching

• Internal Search: Searching is performed on main or primary memory.
• External Search: Searching is performed in secondary memory.

Complexity Analysis

Complexity analysis determines the number of resources (such as time and space) necessary to execute an algorithm.

There are two types of complexities:

1. Time Complexity
2. Space Complexity

Searching Techniques in Data Structures

There are three main types of searching techniques:

1. Linear or Sequential Search
2. Binary Search
3. Interpolation Search

Linear or Sequential Search

This technique searches for an item from a list, starting from the 0th index to the Nth-1 index sequentially. If the item is found, its position is returned; otherwise, -1 or a failure status is returned.

Algorithm

LINEAR_SEARCH (LIST, N, ITEM, LOC, POS)
1. Set POS := 0;
2. Set LOC := 1;
3. Repeat STEPS a and b while LOC <= N
   a. If ( LIST[LOC] = ITEM) then 
      i.   SET POS := LOC;  
      ii.  return;
   b. Otherwise
      i.   SET LOC := LOC + 1;
4. return 

Time Complexity of Linear Search

• Worst Case: C(n) = n
• Average Case: C(n) = n / 2

Linear Search Implementation in C

#include <stdio.h>
#define SIZE 5

int LinearSearch(int ele[], int item) {
    int POS = -1;
    for (int LOC = 0; LOC < SIZE; LOC++) {
        if (ele[LOC] == item) {
            POS = LOC;
            break;
        }
    }
    return POS;
}

int main() {
    int ele[SIZE], item, pos;
    printf("\nEnter Items:\n");
    for (int i = 0; i < SIZE; i++) {
        printf("Enter ELE[%d] : ", i + 1);
        scanf("%d", &ele[i]);
    }

    printf("\n\nEnter Item To Be Searched : ");
    scanf("%d", &item);
    pos = LinearSearch(ele, item);

    if (pos >= 0)
        printf("\nItem Found At Position : %d\n", pos + 1);
    else
        printf("\nItem Not Found In The List\n");

    return 0;
}

Binary Search

Binary search works on a sorted list. It repeatedly divides the search interval in half until the item is found or the interval becomes empty.

Algorithm

BINARY_SEARCH (LIST, N, ITEM, LOC, LOW, MID, HIGH)
1. Set LOW := 1; HIGH := N;
2. Repeat while LOW <= HIGH and ITEM != LIST[MID]
   a. Set MID := (LOW + HIGH)/2
   b. If ITEM = LIST[MID]
       i.   Set LOC := MID
       ii.  Return
   c. If ITEM < LIST[MID]
       i.   Set HIGH := MID - 1;
   d. Otherwise
       i.   Set LOW := MID + 1;
3. SET LOC := NULL
4. return

Time Complexity of Binary Search

• Time Complexity: log₂(n)

Binary Search Implementation in C

#include <stdio.h>
#define SIZE 5

int BinarySearch(int ele[], int item) {
    int POS = -1, LOW = 0, HIGH = SIZE - 1, MID;
    while (LOW <= HIGH) {
        MID = (LOW + HIGH) / 2;
        if (ele[MID] == item) {
            POS = MID;
            break;
        }
        else if (item > ele[MID]) {
            LOW = MID + 1;
        }
        else {
            HIGH = MID - 1;
        }
    }
    return POS;
}

int main() {
    int ele[SIZE], item, pos;
    printf("\nEnter Items:\n");
    for (int i = 0; i < SIZE; i++) {
        printf("Enter ELE[%d] : ", i + 1);
        scanf("%d", &ele[i]);
    }

    printf("\n\nEnter Item To Be Searched : ");
    scanf("%d", &item);
    pos = BinarySearch(ele, item);

    if (pos >= 0)
        printf("\nItem Found At Position : %d\n", pos + 1);
    else
        printf("\nItem Not Found In The List\n");

    return 0;
}

Difference between Linear Search and Binary Search

Linear Search	Binary Search
Sorted list is not required.	Sorted list is required.
Can be used in linked list.	Not suitable for linked list.
Suitable for frequently changing lists.	Suitable for static lists.
High average comparisons.	Low average comparisons.

Interpolation Search

Used when items are uniformly distributed. Improves on binary search by estimating the position of the element.

Interpolation Mid Formula

Mid = low + (high – low) * ((item – LIST[low]) / (LIST[high] – LIST[low]));

Advantages of Interpolation Search

• Average case time complexity is log₂(log₂(n)).
• Better performance than binary search on uniformly distributed data.

Disadvantages of Interpolation Search

• Mid calculation is complex and increases execution time.
• Performs poorly on non-uniformly distributed data.